package com.zjsru.leetcode75.level1;

import java.util.PriorityQueue;

/**
 * @Author: cookLee
 * @Date: 2023-12-03
 * 雇佣 K 位工人的总代价
 * 共进行 k 轮雇佣，且每一轮恰好雇佣一位工人。
 * 在每一轮雇佣中，从最前面 candidates 和最后面 candidates 人中选出代价最小的一位工人，如果有多位代价相同且最小的工人，选择下标更小的一位工人。
 */
public class TotalCost {

    /**
     * 主
     * \
     * 输入：costs = [17,12,10,2,7,2,11,20,8], k = 3, candidates = 4
     * 输出：11
     * 解释：我们总共雇佣 3 位工人。总代价一开始为 0 。
     * - 第一轮雇佣，我们从 [17,12,10,2,7,2,11,20,8] 中选择。最小代价是 2 ，有两位工人，我们选择下标更小的一位工人，即第 3 位工人。总代价是 0 + 2 = 2 。
     * - 第二轮雇佣，我们从 [17,12,10,7,2,11,20,8] 中选择。最小代价是 2 ，下标为 4 ，总代价是 2 + 2 = 4 。
     * - 第三轮雇佣，我们从 [17,12,10,7,11,20,8] 中选择，最小代价是 7 ，下标为 3 ，总代价是 4 + 7 = 11 。注意下标为 3 的工人同时在最前面和最后面 4 位工人中。
     * 总雇佣代价是 11 。
     * \
     * 输入：costs = [1,2,4,1], k = 3, candidates = 3
     * 输出：4
     * 解释：我们总共雇佣 3 位工人。总代价一开始为 0 。
     * - 第一轮雇佣，我们从 [1,2,4,1] 中选择。最小代价为 1 ，有两位工人，我们选择下标更小的一位工人，即第 0 位工人，总代价是 0 + 1 = 1 。注意，下标为 1 和 2 的工人同时在最前面和最后面 3 位工人中。
     * - 第二轮雇佣，我们从 [2,4,1] 中选择。最小代价为 1 ，下标为 2 ，总代价是 1 + 1 = 2 。
     * - 第三轮雇佣，少于 3 位工人，我们从剩余工人 [2,4] 中选择。最小代价是 2 ，下标为 0 。总代价为 2 + 2 = 4 。
     * 总雇佣代价是 4 。
     * \
     * @param args args
     */
    public static void main(String[] args) {
        TotalCost totalCost = new TotalCost();
        int[] costs = new int[]{17, 12, 10, 2, 7, 2, 11, 20, 8};
        int k = 3;
        int candidates = 4;
        System.out.println(totalCost.totalCost(costs, k, candidates));
    }

    public long totalCost(int[] costs, int k, int candidates) {
        long ans = 0L;
        int len = costs.length;

        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> {
            if (a[0] == b[0]) {
                return a[1] - b[1];
            } else {
                return a[0] - b[0];
            }
        });
        //将数组按照candidates的分区来存入数组，并且按照下标的先后顺序存入
        for (int i = 0; i < len; i++) {
            if (i < candidates || i > len - candidates - 1) {
                queue.offer(new int[]{costs[i], i, i < candidates ? 0 : 1});
            }
        }
        //获取分割后左边的最后一位
        int left = candidates - 1;
        //右边的第一个位置
        int right = len - candidates;
        for (int i = 0; i < k; i++) {
            int[] poll = queue.poll();
            int cost = poll[0];
            ans += cost;
            //当左边索引超过或等于右边索引减1时，说明左边和右边的元素已经交叉或相邻，没有足够的元素可以再次分割,即跳过循环
            if (left >= right - 1) {
                continue;
            }
            //获取下标是否优先
            boolean flag = poll[2] == 0;
            //按照取出的范围缩小边界值
            if (flag) {
                left++;
                queue.offer(new int[]{costs[left], left, 0});
            } else {
                right--;
                queue.offer(new int[]{costs[right], right, 1});
            }
        }
        return ans;
    }

}
